1. Field of the Invention
The present invention relates to a processing apparatus for solving optimization problems, such as an optimum structure problem, optimum allocation problem, optimum routing problem, etc., and a method thereof.
2. Description of the Related Art
Recently the solutions to optimization problems have been demanded in a variety of industrial fields. An optimization problem is a problem in which a search is made for a state where a given cost function becomes the maximum or minimum, or a local maximum or local minimum. A problem in which the maximum or a local maximum is searched for can be replaced with a problem in which a search is made for the minimum or a local minimum by changing the sign of a cost function. An optimization problem in which a search is made for the minimum or a local minimum is chiefly described below.
The optimization problem includes, for example, an optimum structure problem, optimum allocation problem, optimum routing problem, optimum network problem, optimum flow problem, optimum cost problem and optimum efficiency problem.
For example, an optimum structure problem is a problem in which a structure in the design of a building, bridge, wing of an airplane, etc., is optimized, and an optimum allocation problem is a problem in which the allocation of facilities in a city designing, the allocation of molecules in a compound, etc., is optimized. An optimum routing problem is a problem in which the routing is optimized in the navigation of vehicles, an electric circuit, etc.
For example, an optimum network problem is a problem in which the piping of gas and water, electric wiring, communications network, etc., is optimized, and an optimum flow problem is a problem in which a traffic flow on a road, a data flow on a network, etc., is optimized. An optimum cost problem and an optimum efficiency problem are problems in which the cost and efficiency in the fields of science, engineering, economy, business, etc., are optimized.
As conventional algorithms for solving such optimization problems, a steepest descent method, a genetic algorithm, a simulated annealing method, etc., are used.
However, the conventional optimization problem algorithms have the following problems.
Conventional information processing apparatuses for solving the optimization problems are roughly classified into two groups: one is the group of problem specifying apparatuses for handling only an individual problem and the other is the group of general-purpose apparatuses for handling a variety of problems. The problem specifying apparatus can be applied only to a specific problem and cannot handle problems other than the specific problem.
However, the general-purpose apparatus is considered to utilize one of the above-described algorithms. Since the steepest descent method presumes that a cost function is differentiable (smooth), the method cannot be applied to problems which are described using an undifferentiable cost function. Since the genetic algorithm has no neighborhood searching capability, the method cannot always be applied to a given problem appropriately. Since it is difficult to control a temperature parameter in the simulated annealing method, the method can hardly integrate a general-purpose parameter control.
The object of the present invention is to provide an easier-to-operate processing apparatus which covers a wider range of optimization problems and a method thereof.
In the first aspect of the present invention, a processing apparatus comprises a creation unit, a storage unit, a deformation unit and an output unit.
The creation unit creates a shape model representing a given problem, and the storage unit stores data on the shape model. The deformation unit deforms the shape model, and the output unit visually outputs the deformed shape model.
In the second aspect of the present invention, a processing apparatus comprises a search unit, a designation unit and an output unit.
The search unit creates a shape model representing a given problem using one or more deformation elements, deforms the shape model while changing the deformation elements, and searches for a solution so as to improve the cost value of the shape model. The designation unit designates a search termination condition for each deformation element, an overall search termination condition, a process sequence of deformation elements, a cost function and a deformation algorithm for deformation elements, and the output unit visually outputs the deformed shape model.